{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**146. LRU Cache**  <font color=red size=3>_hard_</font>\n",
    "\n",
    "Design and implement a data structure for ```Least Recently Used (LRU) cache```. It should support the following operations: ```get``` and ```put```.\n",
    "\n",
    "```get(key)``` - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.\n",
    "```put(key, value)``` - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.\n",
    "\n",
    "**Follow up:**\n",
    "Could you do both operations in **O(1)** time complexity?\n",
    "\n",
    "**Example**\n",
    "\n",
    "```\n",
    "LRUCache cache = new LRUCache( 2 /* capacity */ );\n",
    "\n",
    "cache.put(1, 1);\n",
    "cache.put(2, 2);\n",
    "cache.get(1);       // returns 1\n",
    "cache.put(3, 3);    // evicts key 2\n",
    "cache.get(2);       // returns -1 (not found)\n",
    "cache.put(4, 4);    // evicts key 1\n",
    "cache.get(1);       // returns -1 (not found)\n",
    "cache.get(3);       // returns 3\n",
    "cache.get(4);       // returns 4\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "-1\n",
      "-1\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, key, val):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "        self.pre = None\n",
    "        self.next = None\n",
    "\n",
    "class LRUCache(object):\n",
    "\n",
    "    def __init__(self, capacity):\n",
    "        \"\"\"\n",
    "        :type capacity: int\n",
    "        \"\"\"\n",
    "        self.capacity = capacity\n",
    "        self.map = {}\n",
    "        self.head = Node(None, None)\n",
    "        self.tail = self.head\n",
    "\n",
    "    def get(self, key):\n",
    "        \"\"\"\n",
    "        :type key: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        node = self.map.get(key)\n",
    "        if node:\n",
    "            # move node to tail\n",
    "            node.pre.next = node.next\n",
    "            node.next = None\n",
    "            self.tail.next = node\n",
    "            return node.val\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "    def put(self, key, value):\n",
    "        \"\"\"\n",
    "        :type key: int\n",
    "        :type value: int\n",
    "        :rtype: void\n",
    "        \"\"\"\n",
    "\n",
    "        node = self.get(key)\n",
    "        if node != -1:\n",
    "            node.val = value\n",
    "        else:\n",
    "            if len(self.map) >= self.capacity:\n",
    "                del self.map[self.head.next.key]\n",
    "                self.head.next = self.head.next.next\n",
    "\n",
    "            node = Node(key, value)\n",
    "            if self.head.next is None:\n",
    "                self.head.next = node\n",
    "\n",
    "            node.pre = self.tail\n",
    "            self.tail.next = node\n",
    "            self.tail = node\n",
    "\n",
    "            self.map[key] = node\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    cache = LRUCache(2)\n",
    "    cache.put(1, 1);\n",
    "    cache.put(2, 2);\n",
    "    print(cache.get(1));  # returns 1\n",
    "    cache.put(3, 3);  # evicts key 2\n",
    "    print(cache.get(2));  # returns - 1(not found)\n",
    "    cache.put(4, 4);  # evicts key 1\n",
    "    print(cache.get(1));  # returns - 1(not found)\n",
    "    print(cache.get(3));  # returns 3\n",
    "    print(cache.get(4));  # returns 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
